package com.Twenty_Eight;

/**
 * 79. 单词搜索
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/word-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/09/28 23:43
 */

public class Solution79 {

    public boolean exist(char[][] board, String word) {
        for (int i=0;i<board.length;i++)
        {
            for (int j=0;j<board[i].length;j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (backtracking(i, j, board, word, 0)) return true;
                }
            }
        }
        return false;
    }

    public boolean backtracking(int i,int j,char[][] board,String word,int k){
        if (k==word.length())
        {
            return true;
        }
        if (i<0||i>=board.length||j<0||j>=board[0].length)
        {
            return false;
        }
        if (word.charAt(k)!=board[i][j])
        {
            return false;
        }
        char t=board[i][j];
        board[i][j]='0';
        boolean res=backtracking(i-1,j,board,word,k+1)||backtracking(i+1,j,board,word,k+1)||backtracking(i,j-1,board,word,k+1)
                ||backtracking(i,j+1,board,word,k+1);
        board[i][j]=t;
        return res;
    }

    public static void main(String[] args) {
        char[][] board={
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };
        Solution79 solution79=new Solution79();
        System.out.println(solution79.exist(board,"ABCB"));
    }

}
